package leetcode.pre50;

import java.util.HashSet;
import java.util.Set;

/**
 * 41. 缺失的第一个正数
 * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,2,0]
 * 输出: 3
 * 示例 2:
 * <p>
 * 输入: [3,4,-1,1]
 * 输出: 2
 * 示例 3:
 * <p>
 * 输入: [7,8,9,11,12]
 * 输出: 1
 *
 * @date 2020/4/15 14:47
 */
public class Code41_FindFirstMissNum {
    /**
     * 方式1：使用hash记录。然后从1开始遍历是否在map中
     * 时空都是O(N)
     */
    private static int process(int[] nums) {
        if(nums == null || nums.length == 0)return 1;
        Set<Integer> set = new HashSet<>();
        int max = nums[0];
        for (int e : nums) {
            set.add(e);
            max = Math.max(max, e);
        }
        //处理特殊情况
        if (max <= 0) return 1;
        //有可能是[1,2,3]，那么最后返回max+1
        for (int i = 1; i <= max; i++) {
            if (!set.contains(i)) return i;
        }
        return max + 1;
    }
    //方式2：分两步
    // 第一步：将数据放到他本来应该在的位置，即nums[i]=i+1,
    // (之所以不采用num[i] = i,考虑nums[i]=len情况，会丢失。
    // 采用nums[i]=i+1可以存储nums[len-1]=len)
    //第二步：遍历数组，如果哪个位置nums[i]!=i+1,则他就是缺失的数。
    private static int process2(int[] nums) {
        if(nums == null || nums.length == 0)return 1;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int index = nums[i] - 1;
            while (index >= 0 && index < len && nums[index] != (index + 1)) {
                swap(nums, i, index);//交换略
                index = nums[i] - 1;
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        //indicate nums[len-1] = len
        return len + 1;
    }
    private static void swap(int[] nums, int i, int j) {
        if(i == j) return;
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }



//    方式3：仍然是标记法。但是要做很多预处理。
//    首先，标记法的前提是num[i]属于0-n-1或者1-n之间[处理目标]。
//    题目要求最小的整数，并且数组长度为n。所以数组中负数和大于n的数必定不会影响答案。
//    我们要把数据处理到1-n之间。
//    我们把负数(包含0)和大于n的数都处理成1.
//      【在这之前要判断数组是否有1，没有则返回1，有则进行上述替换】
//    所以现在数组的内容都是1-n之间的了，采用标记法。只标记1次，i=nums[x]标记 i-1位置为负数。
//    然后进行数组的遍历，找到第一个为正数的位置。就是没有出现过该数字。
    private static int process3(int[] nums) {
        if(nums == null || nums.length == 0)return 1;
        int n = nums.length;
        boolean countOne = false;
        for (int i = 0; i < n; i++) {
            if(nums[i] == 1) {
                countOne = true;
                break;
            }
        }
        //如果不包含1，直接返回1
        if(!countOne) return 1;
        //来到这里肯定包含1

        //把负数和大于n的都置为1
        for (int i = 0; i < n; i++) {
            if(nums[i] <=0 || nums[i] > n) nums[i] = 1;
        }
        //采用标记法进行标记，把i =nums[x]对应的 i-1位置进行标记为负数
        for (int i = 0; i < n; i++) {
            int index = Math.abs(nums[i]) - 1;
            if(nums[index] > 0) nums[index] = -nums[index];
        }
        //统计哪个没被标记过
        for (int i = 0; i < n; i++) {
            if(nums[i] > 0) return i+1;
        }
        //indicate 1-n都包含
        return n+1;
    }


}
